import utils.*;

import java.util.*;

public class CodeTop {
    /**
     * mid 3. 无重复字符的最长子串
     */
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        int left = 0, right = 0;
        int max = 0;
        Map<Character, Integer> map = new HashMap<>();
        while (right < len) {
            char c = s.charAt(right);
            if (!map.containsKey(c)) {
                // 如果map中不包括，那么加入
                map.put(c, 1);
            } else {
                // 如果map存在这个c，那么left向右移动，直到他到达重复的那个元素
                while (s.charAt(left) != c) {
                    map.remove(s.charAt(left));
                    left++;
                }
                left++;
            }
            right++;
            max = Math.max(max, right - left);
        }
        return max;
    }

    /**
     * mid 146. LRU 缓存
     */
    static class LRUCache {

        static class DNode {
            public DNode next;
            public DNode prev;
            public int key;
            public int value;

            public DNode(int key, int value) {
                this.value = value;
                this.key = key;
            }
        }

        DNode first;
        DNode tail;
        Map<Integer, DNode> map;
        int cap;
        int size;

        public LRUCache(int capacity) {
            first = new DNode(-1, -1);
            tail = new DNode(-1, -1);
            first.next = tail;
            tail.prev = first;
            map = new HashMap<>();
            cap = capacity;
            size = 0;
        }

        public int get(int key) {
            if (!map.containsKey(key))
                return -1;
            DNode getNode = map.get(key);
            // 移出原先位置
            DNode nodePre = getNode.prev;
            DNode nodeNext = getNode.next;
            nodePre.next = nodeNext;
            nodeNext.prev = nodePre;
            // 移动到开头
            DNode nowFirst = first.next;
            nowFirst.prev = getNode;
            first.next = getNode;
            getNode.prev = first;
            getNode.next = nowFirst;
            return getNode.value;
        }

        public void put(int key, int value) {
            if (map.containsKey(key)) {
                // 存在：更新数值，移动到最前
                // 更新数值
                DNode updateNode = map.get(key);
                updateNode.value = value;
                // 移出原先位置
                DNode nodePre = updateNode.prev;
                DNode nodeNext = updateNode.next;
                nodePre.next = nodeNext;
                nodeNext.prev = nodePre;
                // 移动到开头
                DNode nowFirst = first.next;
                nowFirst.prev = updateNode;
                first.next = updateNode;
                updateNode.prev = first;
                updateNode.next = nowFirst;
            } else {
                // 不存在：放在最前，如果满了，移除最后一个
                if (size == cap) {
                    // 放满了，移出最后一个
                    DNode nowLast = tail.prev;
                    DNode newLast = tail.prev.prev;
                    newLast.next = tail;
                    tail.prev = newLast;
                    // 删除map中的值
                    map.remove(nowLast.key);
                    size--;
                }
                // 放在最前
                DNode nowFirst = first.next;
                DNode newFirst = new DNode(key, value);
                nowFirst.prev = newFirst;
                first.next = newFirst;
                newFirst.prev = first;
                newFirst.next = nowFirst;
                // 加入map
                map.put(key, newFirst);
                size++;
            }
        }
    }


    /**
     * mid 215. 数组中的第K个最大元素
     */
    public int findKthLargest(int[] nums, int k) {
        // 采用三路快排：可以是用三个辅助数组（这样实现很简单），也可以是原数组基础上
        // 作为练习，这里采用原数组的形式
        return findKth3(nums, 0, nums.length - 1, k);
    }

    private int findKth3(int[] nums, int left, int right, int k) {
        Random random = new Random();
        int randomIndex = left + random.nextInt(right - left + 1);
        int pivot = nums[randomIndex];
        int lt = left, ge = right;
        int i = lt;
        while (i <= ge) {
            if (nums[i] < pivot) {
                swap(nums, i, lt);
                i++;
                lt++;
            } else if (nums[i] > pivot) {
                swap(nums, i, ge);
                ge--;
            } else {
                i++;
            }
        }
        // [lt, ge] 区间的数字等于 randomNum
        int bigNum = right - ge, equalNum = ge - lt + 1, smallNum = lt - left;
        if (bigNum >= k)
            return findKth3(nums, ge + 1, right, k);
        else if (bigNum + equalNum >= k)
            return pivot;
        else
            return findKth3(nums, left, lt - 1, k - bigNum - equalNum);
    }

    private void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }


    /**
     * mid 15. 三数之和
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        // -1 -1 0 1
        Arrays.sort(nums);
        int len = nums.length;
        for (int i = 0; i < len - 2; i++) {
            if (i != 0 && nums[i] == nums[i - 1])
                continue;
            int left = i + 1, right = len - 1;
            int target = -nums[i];
            while (left < right) {
                if (left > i + 1 && nums[left] == nums[left - 1]) {
                    left++;
                    continue;
                }
                if (right < len - 1 && nums[right] == nums[right + 1]) {
                    right--;
                    continue;
                }
                if (nums[left] + nums[right] == target) {
                    List<Integer> list = new ArrayList<>();
                    list.add(-target);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    lists.add(list);
                    left++;
                    right--;
                } else if (nums[left] + nums[right] < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return lists;
    }

    /**
     * mid 53. 最大子数组和
     */
    public int maxSubArray(int[] nums) {
        // now 本质上就是 dp 数组, dp[i] = dp[i-1] >= 0 ? dp[i-1] + num : num;
        // dp[i] 表示以 nums[i] 结尾的最大子数组和
        int max = Integer.MIN_VALUE;
        int now = 0;
        for (int num : nums) {
            now = (now >= 0) ? (now + num) : num;
            max = Math.max(max, now);
        }
        return max;
    }

    public int[] maxSubArray_(int[] nums) {
        // 在原题基础上，进一步求这个最大的子数组本身(当然也可以把dp和start数组优化为单个变量)
        int len = nums.length;
        int[] dp = new int[len]; // 和上一题一样,表示以nums[i]结尾的最大子数组和
        int[] start = new int[len]; // 表示以nums[i]结尾的最大字数组的起始下标
        dp[0] = nums[0];
        start[0] = 0;
        for (int i = 1; i < len; i++) {
            if (dp[i - 1] >= 0) {
                dp[i] = dp[i - 1] + nums[i];
                start[i] = start[i - 1];
            } else {
                dp[i] = nums[i];
                start[i] = i;
            }
        }
        // 找到最大的子数组的结尾下标
        int maxIndex = 0;
        int max = dp[0];
        for (int i = 1; i < len; i++) {
            if (dp[i] > max) {
                max = dp[i];
                maxIndex = i;
            }
        }
        return new int[]{start[maxIndex], maxIndex};
    }

    /**
     * mid 912. 排序数组
     */
    public int[] sortArray(int[] nums) {
        // 手撕排序: 快排(直接使用三路快排) & 堆排
        quickSort3Ways(nums, 0, nums.length - 1);
        return nums;
    }

    // 三路快排
    private void quickSort3Ways(int[] nums, int left, int right) {
        if (left > right)
            return;
        int randomIndex = left + new Random().nextInt(right - left + 1);
        int pivot = nums[randomIndex];
        int lt = left, ge = right;
        int i = left;
        while (i <= ge) {
            if (nums[i] < pivot) {
                quickSortSwap(nums, i, lt);
                i++;
                lt++;
            } else if (nums[i] > pivot) {
                quickSortSwap(nums, ge, i);
                ge--;
            } else {
                i++;
            }
        }
        // [lt, ge] 范围内的数字等于 pivot
        quickSort3Ways(nums, left, lt - 1);
        quickSort3Ways(nums, ge + 1, right);
    }

    private void quickSortSwap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }

    // 堆排(排序为从小到大,即建立一个大顶堆,每次把最大的放在最后)
    private int[] sortArrayWithHeap(int[] nums) {
        // 1. 建堆
        buildHeap(nums);
        // 2. 循环,每次把最大的放在最后
        int len = nums.length;
        for (int i = len - 1; i >= 0; i--) {
            heapSortSwap(nums, 0, i);
            heapify(nums, 0, i);
        }
        return nums;
    }

    private void buildHeap(int[] nums) {
        int len = nums.length;
        if (len == 1)
            return;
        int half = (len - 2) / 2;
        for (int i = half; i >= 0; i--) {
            heapify(nums, i, len);
        }
    }

    private void heapify(int[] nums, int pos, int len) {
        // 递归把大的元素放在上面
        int maxPos = pos;
        int leftChild = pos * 2 + 1, rightChild = pos * 2 + 2;
        if (leftChild < len && nums[leftChild] > nums[maxPos])
            maxPos = leftChild;
        if (rightChild < len && nums[rightChild] > nums[maxPos])
            maxPos = rightChild;
        if (maxPos != pos) {
            heapSortSwap(nums, pos, maxPos);
            heapify(nums, maxPos, len);
        }
    }

    private void heapSortSwap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }


    /**
     * mid 5. 最长回文子串
     */
    // 动态规划：时间O(n2)空间O(n2)
    public String longestPalindrome(String s) {
        int len = s.length();
        int maxStart = 0, maxEnd = 0;
        boolean[][] dp = new boolean[len][len]; // dp[i][j] 表示 i-j 是否为回文子串
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
            maxStart = i;
            maxEnd = i;
        }
        for (int i = 0; i < len - 1; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = true;
                maxStart = i;
                maxEnd = i + 1;
            }
        }
        for (int step = 3; step <= len; step++) {
            for (int start = 0; start <= len - step; start++) {
                int end = start + step - 1;
                if (s.charAt(start) == s.charAt(end) && dp[start + 1][end - 1]) {
                    dp[start][end] = true;
                    maxStart = start;
                    maxEnd = end;
                }
            }
        }
        return s.substring(maxStart, maxEnd + 1);
    }

    // 中心扩展算法：时间O(n2)空间O(1)
    public String longestPalindrome_(String s) {
        // 找到所有的边界，即所有的(i, i)和(i, i + 1)
        int len = s.length();
        int maxLen = 0, maxBegin = 0;
        for (int i = 0; i < len; i++) {
            int[] now = expand(s, i, i);
            if (now[0] > maxLen) {
                maxLen = now[0];
                maxBegin = now[1];
            }
        }
        for (int i = 0; i < len - 1; i++) {
            int[] now = expand(s, i, i + 1);
            if (now[0] > maxLen) {
                maxLen = now[0];
                maxBegin = now[1];
            }
        }
        return s.substring(maxBegin, maxBegin + maxLen);
    }

    private int[] expand(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        // 返回扩展后的长度和起始下标
        return new int[]{right - left - 1, left + 1};
    }

    /**
     * easy 1. 两数之和
     */
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>(); // key=target-num  value=index
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if (map.containsKey(nums[i])) {
                return new int[]{map.get(nums[i]), i};
            }
            map.put(target - nums[i], i);
        }
        return null;
    }

    // 手动实现 List<int[]>[] map 每个 List<int[]> 是一个桶,每个桶里可能有很多 int[] = {key,value}
    public int[] twoSum_(int[] nums, int target) {
        int mod = 10007;
        List<int[]>[] map = new List[mod];
        for (int i = 0; i < mod; i++) {
            map[i] = new ArrayList<>();
        }
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            // 如果包含
            int bucket = (nums[i] % mod + mod) % mod;
            if (contains(map, bucket, nums[i])) {
                return new int[]{get(map, bucket, nums[i]), i};
            }
            int putBucket = ((target - nums[i]) % mod + mod) % mod;
            put(map, putBucket, target - nums[i], i);
        }
        return null;
    }

    private boolean contains(List<int[]>[] map, int bucket, int key) {
        for (int[] entry : map[bucket]) {
            if (entry[0] == key)
                return true;
        }
        return false;
    }

    private int get(List<int[]>[] map, int bucket, int key) {
        for (int[] entry : map[bucket]) {
            if (entry[0] == key)
                return entry[1];
        }
        throw new RuntimeException("Key not found in get(" + key + ")");
    }

    private void put(List<int[]>[] map, int bucket, int key, int val) {
        for (int i = 0; i < map[bucket].size(); i++) {
            if (map[bucket].get(i)[0] == key) {
                map[bucket].set(i, new int[]{key, val});
                return;
            }
        }
        map[bucket].add(new int[]{key, val});
    }

    /**
     * mid 33. 搜索旋转排序数组
     */
    public int search(int[] nums, int target) {
        // 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题 二分查找旋转数组
        // nums 中的每个值都 独一无二
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (nums[mid] == target)
                return mid;
            // 如果左面正常
            if (nums[mid] >= nums[left]) {
                if (target >= nums[left] && target <= nums[mid])
                    right = mid - 1;
                else
                    left = mid + 1;
            }
            // 如果右面正常
            else {
                if (target >= nums[mid] && target <= nums[right])
                    left = mid + 1;
                else
                    right = mid - 1;
            }
        }
        return -1;
    }

    /**
     * mid 81. 搜索旋转排序数组 II
     */
    public boolean search_(int[] nums, int target) {
        // 🌟不一样的条件是：nums中可能有重复值
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (nums[mid] == target)
                return true;
            // 0 0 0 0 0 1 2 3 0 这种情况，left、mid、right都是一样的数字，上一题的解法不好区分
            if (nums[mid] == nums[left] && nums[mid] == nums[right]) {
                left++;
                right--;
                continue;
            }
            // 左面正常
            if (nums[mid] >= nums[left]) {
                if (target >= nums[left] && target <= nums[mid])
                    right = mid - 1;
                else
                    left = mid + 1;
            }
            // 右面正常
            else {
                if (target >= nums[mid] && target <= nums[right])
                    left = mid + 1;
                else
                    right = mid - 1;
            }
        }
        return false;
    }

    /**
     * mid 200. 岛屿数量
     */
    // 并查集做法（除此之外的DFS、BFS不在赘述）
    static class UnionSet {
        int[] parent;
        int[] rank;
        int count; // 岛屿数量，也是集合数量，最终会减小为真正的岛屿数量

        public UnionSet(char[][] grid) {
            int m = grid.length, n = grid[0].length;
            count = 0;
            parent = new int[m * n];
            rank = new int[m * n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    int index = i * n + j;
                    if (grid[i][j] == '1') {
                        count++;
                        parent[index] = index;
                    }
                    rank[index] = 0;
                }
            }
        }

        public int findRoot(int index) {
            if (parent[index] != index)
                parent[index] = findRoot(parent[index]);
            return parent[index];
        }

        public void union(int index1, int index2) {
            int root1 = findRoot(index1);
            int root2 = findRoot(index2);
            if (root1 == root2)
                return;
            if (rank[root1] == rank[root2]) {
                rank[root1]++;
                parent[root2] = root1;
            } else if (rank[root1] > rank[root2]) {
                parent[root2] = root1;
            } else {
                parent[root1] = root2;
            }
            // 这两个的根不一样，合并了，集合数量减一
            count--;
        }
    }

    public int numIslands(char[][] grid) {
        UnionSet unionSet = new UnionSet(grid);
        int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        int m = grid.length, n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != '1')
                    continue;
                grid[i][j] = '0';
                for (int[] dir : dirs) {
                    int newI = i + dir[0], newJ = j + dir[1];
                    if (newI >= 0 && newI < m && newJ >= 0 && newJ < n && grid[newI][newJ] == '1') {
                        int index = i * n + j;
                        int indexNew = newI * n + newJ;
                        unionSet.union(indexNew, index);
                    }
                }
            }
        }
        return unionSet.count;
    }

    /**
     * mid 46. 全排列
     */
    public List<List<Integer>> permute(int[] nums) {
        int len = nums.length;
        List<List<Integer>> lists = new ArrayList<>();
        boolean[] visit = new boolean[len];
        permuteDFS(nums, new ArrayList<>(), lists, visit);
        return lists;
    }

    private void permuteDFS(int[] nums, List<Integer> list, List<List<Integer>> lists, boolean[] visit) {
        if (list.size() == nums.length) {
            lists.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (visit[i])
                continue;
            visit[i] = true;
            list.add(nums[i]);
            permuteDFS(nums, list, lists, visit);
            list.remove(list.size() - 1);
            visit[i] = false;
        }
    }

    /**
     * 20. 有效的括号
     */
    public boolean isValid(String s) {
        int len = s.length();
        Deque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            switch (c) {
                case '(', '[', '{' -> stack.push(c);
                case ')' -> {
                    if (!stack.isEmpty() && stack.peek() == '(')
                        stack.pop();
                    else
                        return false;
                }
                case ']' -> {
                    if (!stack.isEmpty() && stack.peek() == '[')
                        stack.pop();
                    else
                        return false;
                }
                case '}' -> {
                    if (!stack.isEmpty() && stack.peek() == '{')
                        stack.pop();
                    else
                        return false;
                }
            }
        }
        return stack.isEmpty();
    }

    /**
     * easy 88. 合并两个有序数组
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // 把nums2合并到nums1中去（nums1的长度为m+n）
        // 为了不用辅助数组，需要逆向双指针遍历，找最大的添在最后
        int pos1 = m - 1, pos2 = n - 1;
        int insert = m + n - 1;
        while (pos1 >= 0 && pos2 >= 0) {
            if (nums1[pos1] >= nums2[pos2]) {
                nums1[insert] = nums1[pos1];
                pos1--;
            } else {
                nums1[insert] = nums2[pos2];
                pos2--;
            }
            insert--;
        }
        // 这里不用判断 pos1 >= 0 的另一种情况，因为那说明左面剩下的就是nums1，已经ok了，我们要的就是nums1
        while (pos2 >= 0) {
            nums1[insert] = nums2[pos2];
            insert--;
            pos2--;
        }
    }

    public void merge_distinct(int[] nums1, int m, int[] nums2, int n) {
        // 🌟把nums2合并到nums1中去，去重
        // 还是逆向双指针，最后去重后集中在右面，再挪到前面来
    }

    /**
     * easy 121. 买卖股票的最佳时机
     */
    // 只能买卖一次
    public int maxProfit(int[] prices) {
        int len = prices.length;
        int[] buy = new int[len];
        int[] sell = new int[len];
        buy[0] = -prices[0];
        sell[0] = 0;
        for (int i = 1; i < len; i++) {
            buy[i] = Math.max(buy[i - 1], -prices[i]);
            sell[i] = Math.max(sell[i - 1], buy[i] + prices[i]);
        }
        return sell[len - 1];
    }

    // 买卖k次
    public int maxProfit_K(int k, int[] prices) {
        int len = prices.length;
        int[][] buy = new int[k][len];
        int[][] sell = new int[k][len];
        for (int i = 0; i < k; i++) {
            buy[i][0] = -prices[0];
            sell[i][0] = 0;
        }
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < k; j++) {
                buy[j][i] = Math.max(buy[j][i - 1], (j == 0 ? 0 : sell[j - 1][i]) - prices[i]);
                sell[j][i] = Math.max(sell[j][i - 1], buy[j][i] + prices[i]);
            }
        }
        return sell[k - 1][len - 1];
    }

    /**
     * 122. 买卖股票的最佳时机 II 无限制买卖次数
     */
    public int maxProfit2(int[] prices) {
        int len = prices.length;
        int[] have = new int[len]; // 当天持有股票的最大利润
        int[] no = new int[len]; // 当天未持有股票的最大利润
        have[0] = -prices[0];
        no[0] = 0;
        for (int i = 1; i < len; i++) {
            have[i] = Math.max(have[i - 1], no[i - 1] - prices[i]);
            no[i] = Math.max(no[i - 1], have[i - 1] + prices[i]);
        }
        return no[len - 1];
    }

    /**
     * mid 300. 最长递增子序列
     */
    // 直接采用“贪心”，minValue[i]表示长度为i+1的子序列的末尾最小值
    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        int[] minValue = new int[len];
        int maxLen = 0;
        for (int num : nums) {
            int left = 0, right = maxLen - 1;
            int insertIndex = maxLen;
            while (left <= right) {
                int mid = (right - left) / 2 + left;
                if (num <= minValue[mid]) {
                    insertIndex = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            minValue[insertIndex] = num;
            if (insertIndex == maxLen)
                maxLen++;
        }
        return maxLen;
    }

    // 如果需要返回具体的路径，那么这么写
    public List<Integer> lengthOfLISWithPath(int[] nums) {
        int len = nums.length;
        int[] minValue = new int[len];         // minValue[i]：长度为 i+1 的序列的最小末尾值
        int[] minIndex = new int[len];         // minIndex[i]：该最小末尾值的原始位置
        int[] prev = new int[len];             // prev[i]：nums[i] 前一个组成 LIS 的元素下标

        int maxLen = 0; // 当前最长递增子序列长度
        Arrays.fill(prev, -1); // 初始化前驱

        for (int i = 0; i < len; i++) {
            int left = 0, right = maxLen - 1;
            int insertIndex = maxLen;
            while (left <= right) {
                int mid = (right - left) / 2 + 1;
                if (nums[i] <= minValue[mid]) {
                    insertIndex = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }

            // 🌟🌟🌟🌟🌟
            minValue[insertIndex] = nums[i];
            minIndex[insertIndex] = i;
            if (insertIndex > 0) {
                prev[i] = minIndex[insertIndex - 1]; // i 的前驱是更短 LIS 的末尾
            }
            if (insertIndex == maxLen) {
                maxLen++; // 找到更长的 LIS
            }
        }

        // 回溯路径
        List<Integer> lis = new ArrayList<>();
        int k = minIndex[maxLen - 1]; // 最长 LIS 的末尾元素位置
        while (k >= 0) {
            lis.add(nums[k]);
            k = prev[k];
        }
        Collections.reverse(lis);
        return lis;
    }

    /**
     * mid 54. 螺旋矩阵
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        // 1 <= m, n <= 10
        int m = matrix.length, n = matrix[0].length;
        int count = m * n;
        // 没说不能修改，直接在原数组改；如果不能修改就辅助数组
        List<Integer> list = new ArrayList<>();
        int i = 0, j = 0;
        int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 这四个方向有顺序
        int dirIndex = 0;
        while (count > 0) {
            int num = matrix[i][j];
            list.add(num);
            matrix[i][j] = Integer.MAX_VALUE; // 设定max_value为遍历过
            int newI = i + dir[dirIndex][0];
            int newJ = j + dir[dirIndex][1];
            if (newI < 0 || newI >= m || newJ < 0 || newJ >= n || matrix[newI][newJ] == Integer.MAX_VALUE) {
                dirIndex = (dirIndex + 1) % 4;
                newI = i + dir[dirIndex][0];
                newJ = j + dir[dirIndex][1];
            }
            i = newI;
            j = newJ;
            count--;
        }

        return list;
    }

    // 🌟🌟如果不让修改原数组，也要求O(1)空间复杂度不让辅助数组的话：一圈一圈遍历，其实递归应该更符合直觉，但是也有空间复杂度
    public List<Integer> spiralOrder_(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int steps = (Math.min(m, n) + 1) / 2; // 🌟🌟
        List<Integer> list = new ArrayList<>();
        // 如果 steps == 0，说明是 1xn mx1 的情况，直接返回得了
        if (steps == 0) {
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    list.add(matrix[i][j]);
                }
            }
            return list;
        }
        // steps>0 说明至少是有个圈的
        for (int step = 0; step < steps; step++) {
            // 确定圈的位置和大小，以及元素数量。当前圈的大小为 m n
            int i = step, j = step; // 起始位置
            // 先定义四个边界
            int maxM = step + m - 1;
            int maxN = step + n - 1;
            int minM = step;
            int minN = step;
            // 如果是 1 x n 或者 m x 1 的圈，说明是最后一圈了，直接遍历返回
            if (m == 1) {
                // 1 x n
                for (int k = j; k <= maxN; k++) {
                    list.add(matrix[i][k]);
                }
                continue;
            } else if (n == 1) {
                // m x 1
                for (int k = i; k <= maxM; k++) {
                    list.add(matrix[k][j]);
                }
                continue;
            }
            // 遍历这个圈
            int count = 2 * m + 2 * n - 4; // 当前圈的元素数量
            int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
            int dirIndex = 0;
            while (count > 0) {
                int num = matrix[i][j];
                list.add(num);
                // 得到下一个位置
                int newI = i + dir[dirIndex][0];
                int newJ = j + dir[dirIndex][1];
                if (newI < minM || newI > maxM || newJ < minN || newJ > maxN) {
                    dirIndex++;
                    newI = i + dir[dirIndex][0];
                    newJ = j + dir[dirIndex][1];
                }
                i = newI;
                j = newJ;
                // 循环条件
                count--;
            }
            // 下一圈缩小
            m -= 2;
            n -= 2;
        }
        return list;
    }

    /**
     * easy 415. 字符串相加
     */
    public String addStrings(String num1, String num2) {
        StringBuilder sb = new StringBuilder();
        int next = 0;
        int pos1 = num1.length() - 1, pos2 = num2.length() - 1;
        while (pos1 >= 0 && pos2 >= 0) {
            int n1 = num1.charAt(pos1) - '0';
            int n2 = num2.charAt(pos2) - '0';
            int add = n1 + n2 + next;
            int digit = add % 10;
            sb.append(digit);
            next = add / 10;
            pos1--;
            pos2--;
        }
        while (pos1 >= 0) {
            int n = num1.charAt(pos1) - '0';
            int add = n + next;
            int digit = add % 10;
            sb.append(digit);
            next = add / 10;
            pos1--;
        }
        while (pos2 >= 0) {
            int n = num2.charAt(pos2) - '0';
            int add = n + next;
            int digit = add % 10;
            sb.append(digit);
            next = add / 10;
            pos2--;
        }
        if (next != 0)
            sb.append(next);
        return sb.reverse().toString();
    }

    /**
     * easy 56. 合并区间
     */
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (o1, o2) -> Integer.compare(o1[0], o2[0]));
        List<int[]> list = new ArrayList<>();
        int len = intervals.length;
        int left = intervals[0][0], right = intervals[0][1];
        for (int i = 1; i < len; i++) {
            if (intervals[i][0] <= right) {
                right = Math.max(right, intervals[i][1]);
            } else {
                list.add(new int[]{left, right});
                left = intervals[i][0];
                right = intervals[i][1];
            }
        }
        list.add(new int[]{left, right});
        int ansSize = list.size();
        int[][] ans = new int[ansSize][2];
        for (int i = 0; i < ansSize; i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }

    /**
     * easy 160. 相交链表
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 如果不能用 set 记录遍历过的节点，那么就采用这种办法
        if (headA == null || headB == null)
            return null;
        ListNode nodeA = headA, nodeB = headB;
        while (nodeA != nodeB) {
            nodeA = nodeA == null ? nodeB : nodeA.next;
            nodeB = nodeB == null ? nodeA : nodeB.next;
        }
        return nodeA;
    }

    /**
     * hard 42. 接雨水
     */
    // 1. 左右双指针
    public int trap(int[] height) {
        // 左右双指针，每次选择最矮的部分，去掉，往里一格，维护左右指针相当于两面墙
        int left = 0, right = height.length - 1;
        int leftWall = height[left], rightWall = height[right];
        int rain = 0;
        while (left < right) {
            if (leftWall < rightWall) {
                left++;
                // 如果新位置比之前的墙矮，则加上这么多雨水，否则更新墙高
                if (height[left] < leftWall)
                    rain += leftWall - height[left];
                else
                    leftWall = height[left];
            } else {
                right--;
                if (height[right] < rightWall)
                    rain += rightWall - height[right];
                else
                    rightWall = height[right];
            }
        }
        return rain;
    }

    // 2. 单调栈
    public int trap_(int[] height) {
        // 下降时正常入栈，发现上升时处理
        Deque<Integer> stack = new LinkedList<>();
        int rain = 0;
        int len = height.length;
        for (int i = 0; i < len; i++) {
            // 要找到第一个比当前（右墙）小的，作为底边，第二个作为左墙
            while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
                int bottom = stack.pop();
                if (stack.isEmpty())
                    break;
                int left = stack.peek();
                rain += (Math.min(height[i], height[left]) - height[bottom]) * (i - left - 1);
            }
            stack.push(i);
        }
        return rain;
    }

    /**
     * mid-hard 72. 编辑距离
     */
    public int minDistance(String word1, String word2) {
        // dp[i][j] 表示 word1 的前i个 和 word2 的前j个 互相转换所需最小步骤距离
        int n1 = word1.length(), n2 = word2.length();
        int[][] dp = new int[n1 + 1][n2 + 1];
        // 初始化：一边取零个字符，这样变为另一边就全是添加操作
        for (int i = 0; i <= n1; i++)
            dp[i][0] = i;
        for (int i = 0; i <= n2; i++)
            dp[0][i] = i;
        // dp：有三种操作
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                int delete = 1 + dp[i - 1][j];
                int insert = 1 + dp[i][j - 1];
                int modify = 1 + dp[i - 1][j - 1];
                // 如果word1[i]==word2[j]
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    modify--;
                }
                dp[i][j] = Math.min(delete, Math.min(insert, modify));
            }
        }
        return dp[n1][n2];
    }

    /**
     * mid 93. 复原 IP 地址
     */
    public List<String> restoreIpAddresses(String s) {
        // 使用dfs+回溯
        List<String> stringList = new ArrayList<>();
        backTraceIP(s, stringList, new ArrayList<>(), 0);
        return stringList;
    }

    private void backTraceIP(String s, List<String> stringList, List<String> list, int index) {
        if (index == s.length() && list.size() == 4) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 4; i++) {
                if (i != 0)
                    sb.append('.');
                sb.append(list.get(i));
            }
            stringList.add(sb.toString());
            return;
        }
        if (index >= s.length() || list.size() >= 4)
            return;
        for (int i = index; i < s.length() && i < index + 3; i++) {
            String temp = s.substring(index, i + 1);
            // 不能有前导0
            if (temp.length() > 1 && temp.charAt(0) == '0')
                continue;
            // 不能大于255
            if (Integer.parseInt(temp) > 255)
                continue;
            list.add(temp);
            backTraceIP(s, stringList, list, i + 1);
            list.remove(list.size() - 1);
        }
    }

    /**
     * hard 4. 寻找两个正序数组的中位数
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 在这两个数组里,找第k大的数字
        int len = nums1.length + nums2.length;
        if (len % 2 == 0) {
            return (findKthNum(nums1, 0, nums2, 0, len / 2) + findKthNum(nums1, 0, nums2, 0, len / 2 + 1)) / 2.0;
        } else {
            return findKthNum(nums1, 0, nums2, 0, len / 2 + 1);
        }
    }

    private int findKthNum(int[] nums1, int index1, int[] nums2, int index2, int k) {
        // 如果有一个数组到头了,直接根据另一个数组返回第k大的值
        if (index1 == nums1.length)
            return nums2[index2 + k - 1];
        if (index2 == nums2.length)
            return nums1[index1 + k - 1];
        // 如果找第一个,返回小的即可
        if (k == 1)
            return Math.min(nums1[index1], nums2[index2]);
        // 找两个数组分别的第 k / 2 个
        int pos1 = Math.min(nums1.length - 1, index1 + k / 2 - 1);
        int pos2 = Math.min(nums2.length - 1, index2 + k / 2 - 1);
        if (nums1[pos1] < nums2[pos2]) {
            return findKthNum(nums1, pos1 + 1, nums2, index2, k - (pos1 - index1 + 1));
        } else {
            return findKthNum(nums1, index1, nums2, pos2 + 1, k - (pos2 - index2 + 1));
        }
    }

    /**
     * mid 22. 括号生成
     */
    public List<String> generateParenthesis(int n) {
        List<String> stringList = new ArrayList<>();
        findParenthesis(stringList, new StringBuilder(), 0, 0, n);
        return stringList;
    }

    private void findParenthesis(List<String> stringList, StringBuilder sb, int leftNum, int rightNum, int n) {
        if (leftNum == n && rightNum == n) {
            stringList.add(sb.toString());
            return;
        }
        // 左括号数量小于n就能添加
        if (leftNum < n) {
            sb.append('(');
            findParenthesis(stringList, sb, leftNum + 1, rightNum, n);
            sb.deleteCharAt(sb.length() - 1);
        }
        // 右括号数量小于左括号就能添加
        if (rightNum < leftNum) {
            sb.append(')');
            findParenthesis(stringList, sb, leftNum, rightNum + 1, n);
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    /**
     * mid 31. 下一个排列
     */
    public void nextPermutation(int[] nums) {
        // 1 <= nums.length <= 100  0 <= nums[i] <= 100
        int len = nums.length;
        // 从右往左找，递增就继续找，直到找到小于的，把它和最小的比他大的元素交换位置，然后后面这些reverse
        // example  1  2  3  7  6  5  4
        //          1  2 [3] 7  6  5 '4'
        //          1  2  4  7  6  5  3
        //          1  2  4  3  5  6  7
        int num = 0;
        for (int i = len - 1; i >= 0; i--) {
            if (nums[i] >= num) {
                num = nums[i];
            } else {
                // 找到小的了
                int findPos = i + 1;
                int smallestBiggerPos = findPos;
                while (findPos < len) {
                    if (nums[findPos] > nums[i]) smallestBiggerPos = findPos;
                    else break;
                    findPos++;
                }
                // 交换
                swapIntList(nums, i, smallestBiggerPos);
                // 翻转
                reverseIntList(nums, i + 1, len - 1);
                return;
            }
        }
        // 如果是类似 5 4 3 2 1 这样的
        reverseIntList(nums, 0, len - 1);
    }

    private void swapIntList(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }

    private void reverseIntList(int[] nums, int left, int right) {
        if (left >= right)
            return;
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }

    /**
     * easy 69. x 的平方根
     */
    public int mySqrt(int x) {
        // 二分查找
        int left = 0, right = x;
        int pos = left;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            // 找到和他相等或第一个比他小的数字（和插入位置相反）
            if ((long) mid * mid <= x) {
                pos = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return pos;
    }

    /**
     * mid 239. 滑动窗口最大值
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 1. 建堆 nlogn  2. 双端队列 n
        // 双端队列，最左面的元素是最大的，每次往右面加元素
        Deque<Integer> deque = new ArrayDeque<>();
        int len = nums.length;
        int[] ans = new int[len - k + 1];
        for (int i = 0; i < len; i++) {
            // 先把超出索引的元素去掉
            while (!deque.isEmpty() && deque.peekFirst() <= i - k)
                deque.removeFirst();
            // 如果当前元素大于右面的元素，去掉右面的元素
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()])
                deque.removeLast();
            deque.addLast(i);
            // 获得答案
            if (i >= k - 1)
                ans[i - k + 1] = nums[deque.peekFirst()];
        }
        return ans;
    }

    /**
     * mid 8. 字符串转换整数 (atoi)
     */
    public int myAtoi(String s) {
        // s 由英文字母（大写和小写）、数字（0-9）、' '、'+'、'-' 和 '.' 组成
        int len = s.length();
        int ans = 0;
        boolean isMinus = false;
        int pos = 0;
        // 处理空格
        while (pos < len) {
            if (s.charAt(pos) != ' ')
                break;
            pos++;
        }
        // 处理符号
        if (pos < len && (s.charAt(pos) == '+' || s.charAt(pos) == '-')) {
            if (s.charAt(pos) == '-')
                isMinus = true;
            pos++;
        }
        // 只接受数字
        while (pos < len) {
            char c = s.charAt(pos);
            if (Character.isDigit(c)) {
                int num = c - '0';
                // 处理溢出：正 ans * 10 + num <= max 负 -(ans * 10 + num) >= min ➡️ -ans * 10 >= min + num
                if (!isMinus && ans > (Integer.MAX_VALUE - num) / 10) {
                    return Integer.MAX_VALUE;
                }
                if (isMinus && -ans < (Integer.MIN_VALUE + num) / 10) {
                    return Integer.MIN_VALUE;
                }
                ans = 10 * ans + num;
                pos++;
            } else break;
        }
        // 处理正负
        return isMinus ? -ans : ans;
    }

    /**
     * easy 2. 两数相加
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 每个链表中的节点数在范围 [1, 100] 内
        ListNode dummy = new ListNode();
        ListNode p = dummy;
        int step = 0;
        while (l1 != null && l2 != null) {
            int sum = l1.val + l2.val + step;
            int num = sum % 10;
            step = sum / 10;
            p.next = new ListNode(num);
            p = p.next;
            l1 = l1.next;
            l2 = l2.next;
        }
        while (l1 != null) {
            int sum = l1.val + step;
            int num = sum % 10;
            step = sum / 10;
            p.next = new ListNode(num);
            p = p.next;
            l1 = l1.next;
        }
        while (l2 != null) {
            int sum = l2.val + step;
            int num = sum % 10;
            step = sum / 10;
            p.next = new ListNode(num);
            p = p.next;
            l2 = l2.next;
        }
        if (step > 0) {
            p.next = new ListNode(step);
        }
        return dummy.next;
    }

    /**
     * hard 32. 最长有效括号
     */
    public int longestValidParentheses(String s) {
        // 动态规划，dp[i]表示以s.charAt(i)结尾的满足条件的最大子数组长度
        int len = s.length();
        int[] dp = new int[len];
        int max = 0;
        for (int i = 1; i < len; i++) {
            char c = s.charAt(i), prev = s.charAt(i - 1);
            // 当前是 ( dp为0，当前是 ) 处理
            if (c == ')') {
                // 如果前一个为 ( 则 dp[i] = dp[i-2] + 2;
                if (prev == '(') {
                    dp[i] = 2;
                    if (i >= 2)
                        dp[i] += dp[i - 2];
                }
                // 如果前一个为 ) 且 s[i-dp[i-1]-1] 是 ( 则 dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2
                else {
                    if (i - dp[i - 1] - 1 >= 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                        dp[i] = dp[i - 1] + 2;
                        if (i - dp[i - 1] - 2 >= 0)
                            dp[i] += dp[i - dp[i - 1] - 2];
                    }
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }

    /**
     * mid 43. 字符串相乘
     */
    public String multiply(String num1, String num2) {
        // n1位✖️n2位，最多为（n1+n2）位
        if (num1.equals("0") || num2.equals("0"))
            return "0";
        int len1 = num1.length(), len2 = num2.length();
        int[] ans = new int[len1 + len2];
        for (int i = len1 - 1; i >= 0; i--) {
            for (int j = len2 - 1; j >= 0; j--) {
                int number1 = num1.charAt(i) - '0';
                int number2 = num2.charAt(j) - '0';
                int multi = number1 * number2;
                ans[i + j + 1] += multi % 10;
                ans[i + j] += multi / 10;
            }
        }
        // 超过10的进位
        for (int i = len1 + len2 - 1; i >= 1; i--) {
            if (ans[i] >= 10) {
                int temp = ans[i];
                ans[i] = temp % 10;
                ans[i - 1] += temp / 10;
            }
        }
        // 得到字符串
        StringBuilder sb = new StringBuilder();
        boolean flag = false;
        for (int i = 0; i < len1 + len2; i++) {
            if (ans[i] == 0 && !flag)
                continue;
            sb.append(ans[i]);
            flag = true;
        }
        return sb.toString();
    }

    /**
     * hard 76. 最小覆盖子串
     */
    public String minWindow(String s, String t) {
        // 滑动窗口
        int slen = s.length(), tlen = t.length();
        int left = 0, right = 0;
        Map<Character, Integer> map = new HashMap<>(), nowMap = new HashMap<>();
        for (int i = 0; i < tlen; i++) {
            map.put(t.charAt(i), map.getOrDefault(t.charAt(i), 0) + 1);
        }
        int hit = 0;
        int min = Integer.MAX_VALUE;
        int minLeft = 0, minRight = 0;
        String ans = "";
        while (right < slen) {
            if (map.containsKey(s.charAt(right))) {
                nowMap.put(s.charAt(right), nowMap.getOrDefault(s.charAt(right), 0) + 1);
                if (Objects.equals(nowMap.get(s.charAt(right)), map.get(s.charAt(right))))
                    hit++;
                while (hit == map.size()) {
                    if (right - left + 1 < min) {
                        min = right - left + 1;
                        minLeft = left;
                        minRight = right;
                    }
                    char leftChar = s.charAt(left);
                    if (map.containsKey(leftChar)) {
                        nowMap.put(leftChar, nowMap.get(leftChar) - 1);
                        if (nowMap.get(leftChar) < map.get(leftChar))
                            hit--;
                    }
                    left++;
                }
            }
            right++;
        }
        return min == Integer.MAX_VALUE ? "" : s.substring(minLeft, minRight + 1);
    }

    /**
     * hard 41. 缺失的第一个正数
     */
    public int firstMissingPositive(int[] nums) {
        // 采用标负代表这个位置有数字
        int n = nums.length;
        // 把条件之外的数字全部标为最大值
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0 || nums[i] > n)
                nums[i] = Integer.MAX_VALUE;
        }
        // 把所有符合范围的数字的对应下标标负
        for (int i = 0; i < n; i++) {
            int num = Math.abs(nums[i]);
            if (num > 0 && num <= n) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }
        // 找到第一个不是负的位置，即为缺失的第一个正整数
        int lack = 1;
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0)
                break;
            lack++;
        }
        return lack;
    }

    public int firstMissingPositive_(int[] nums) {
        // 把不属于数组长度范围内的数字清除：假设数组长度为3，那么缺失的正整数最小就是1，最大就是3
        // -1 代表当前位置为空
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0 || nums[i] > n)
                nums[i] = -1;
        }
        // 遍历，确定哪些位置的正整数存在
        for (int i = 0; i < n; i++) {
            while (nums[i] != -1 && nums[i] != i + 1) {
                int num = nums[i];
                // 不和自己交换
                if (nums[num - 1] == num) {
                    nums[i] = -1;
                    break;
                }
                // 交换
                int temp = nums[num - 1];
                nums[num - 1] = num;
                nums[i] = temp;
            }
        }
        // 遍历，找到缺失的最小正整数
        int lack = 1;
        for (int num : nums) {
            if (num == -1)
                break;
            lack++;
        }
        return lack;
    }

    /**
     * mid 151. 反转字符串中的单词
     */
    public String reverseWords(String s) {
        // 简单解法：s=s.trim();s=去除多余空格;list=s.split(' ');
        // 去除左右前导空格
        s = s.trim();
        // 去除中间多余空格
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (i > 0 && s.charAt(i) == ' ' && s.charAt(i - 1) == ' ')
                continue;
            sb.append(s.charAt(i));
        }
        // 翻转每个单词
        int wordStart = 0;
        for (int i = 0; i < sb.length(); i++) {
            if (sb.charAt(i) == ' ' || i == sb.length() - 1) {
                // wordStart 到 i-1 的一个单词翻转
                int left = wordStart;
                int right = i == sb.length() - 1 ? i : i - 1;
                while (left < right) {
                    char temp = sb.charAt(left);
                    sb.setCharAt(left, sb.charAt(right));
                    sb.setCharAt(right, temp);
                    left++;
                    right--;
                }
                wordStart = i + 1;
            }
        }
        // 翻转全部，得到答案
        return sb.reverse().toString();
    }

    /**
     * mid 78. 子集
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        getSubsets(nums, lists, new ArrayList<>(), 0);
        return lists;
    }

    private void getSubsets(int[] nums, List<List<Integer>> lists, List<Integer> list, int pos) {
        lists.add(new ArrayList<>(list));
        for (int i = pos; i < nums.length; i++) {
            list.add(nums[i]);
            getSubsets(nums, lists, list, i + 1);
            list.remove(list.size() - 1);
        }
    }

    /**
     * mid 90. 子集 II
     */
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> lists = new ArrayList<>();
        getSubsetsWithDup(nums, lists, new ArrayList<>(), 0);
        return lists;
    }

    private void getSubsetsWithDup(int[] nums, List<List<Integer>> lists, List<Integer> list, int pos) {
        lists.add(new ArrayList<>(list));
        for (int i = pos; i < nums.length; i++) {
            if (i > pos && nums[i] == nums[i - 1])
                continue;
            list.add(nums[i]);
            getSubsetsWithDup(nums, lists, list, i + 1);
            list.remove(list.size() - 1);
        }
    }

    /**
     * easy 155. 最小栈
     */
    static class MinStack {

        Deque<Integer> stack;
        Deque<Integer> minStack;

        public MinStack() {
            stack = new LinkedList<>();
            minStack = new LinkedList<>();
        }

        public void push(int val) {
            stack.push(val);
            if (minStack.isEmpty())
                minStack.push(val);
            else
                minStack.push(Math.min(minStack.peek(), val));
        }

        public void pop() {
            stack.pop();
            minStack.pop();
        }

        public int top() {
            return stack.peek();
        }

        public int getMin() {
            return minStack.peek();
        }
    }

    /**
     * mid 34. 在排序数组中查找元素的第一个和最后一个位置
     */
    public int[] searchRange(int[] nums, int target) {
        int[] ans = new int[2];
        // 找元素的第一个位置
        int left = 0, right = nums.length - 1;
        int firstPos = -1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (target <= nums[mid]) {
                if (target == nums[mid])
                    firstPos = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // 找元素的第二个位置
        left = 0;
        right = nums.length - 1;
        int lastPos = -1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (nums[mid] <= target) {
                if (nums[mid] == target)
                    lastPos = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        ans[0] = firstPos;
        ans[1] = lastPos;
        return ans;
    }

    /**
     * mid 101. 对称二叉树
     */
    public boolean isSymmetric(TreeNode root) {
        // 递归
        if (root == null)
            return true;
        return isOK(root.left, root.right);
    }

    private boolean isOK(TreeNode node1, TreeNode node2) {
        if (node1 == null && node2 == null)
            return true;
        if (node1 == null || node2 == null)
            return false;
        if (node1.val != node2.val)
            return false;
        return isOK(node1.left, node2.right) && isOK(node1.right, node2.left);
    }

    public boolean isSymmetric_(TreeNode root) {
        // 非递归
        if (root == null)
            return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);
        while (!queue.isEmpty()) {
            TreeNode node1 = queue.poll();
            TreeNode node2 = queue.poll();
            if (node1 == null && node2 == null)
                continue;
            if (node1 == null || node2 == null)
                return false;
            if (node1.val != node2.val)
                return false;
            queue.offer(node1.left);
            queue.offer(node2.right);
            queue.offer(node1.right);
            queue.offer(node2.left);
        }
        return true;
    }

    /**
     * mid 394. 字符串解码
     */
    public String decodeString(String s) {
        Deque<Integer> numStack = new ArrayDeque<>();
        Deque<String> prevStack = new ArrayDeque<>();
        StringBuilder sb = new StringBuilder();
        int len = s.length();
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                int pos = i;
                int num = 0;
                while (Character.isDigit(s.charAt(pos))) {
                    num = num * 10 + (s.charAt(pos) - '0');
                    pos++;
                }
                i = pos; // 此时指向[
                prevStack.push(sb.toString());
                sb = new StringBuilder();
                numStack.push(num);
            } else if (c == ']') {
                int times = numStack.pop();
                String prev = prevStack.pop();
                sb = new StringBuilder(prev + sb.toString().repeat(times));
            } else {
                sb.append(c);
            }
        }
        return sb.toString();
    }

    /**
     * mid 470. 用 Rand7() 实现 Rand10()
     */
    public int rand7() {
        return new Random().nextInt(7) + 1;
    }

    public int rand10() {
        // 拒绝采样
        // 直接用十个rand7()的和然后除以7，最后的结果是[1,10]，但是每个数字的概率不一样，不能这么干，要想办法让每个数字的概率一样
        // 用两个rand7()，每个数字代表7进制下的一位数字，即 7 * num1 + num2，这样得到的七七四十九种可能都是相等的概率1/49
        // 我们需要[1,10]，则拒绝采样，直到答案为这个范围内才返回
        while (true) {
            int ran1 = rand7(), ran2 = rand7();
            int ans = (ran1 - 1) * 7 + (ran2 - 1); // 得到的这个ans不论是多少都是概率相同的
            if (ans >= 1 && ans <= 10)
                return ans;
        }
    }

    public int rand10_() {
        while (true) {
            int ran1 = rand7(), ran2 = rand7();
            int ans = (ran1 - 1) * 7 + (ran2 - 1); // 得到的这个ans不论是多少都是概率相同的
            if (ans >= 1 && ans <= 40) // 这 1-10 11-20 21-30 31-40 都是一样的概率
                return (ans % 10) + 1;
        }
    }

    /**
     * mid 39. 组合总和
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // 2 <= candidates[i] <= 40
        // 无重复元素 元素可重复使用
        List<List<Integer>> lists = new ArrayList<>();
        getCombinationSum(candidates, 0, target, new ArrayList<>(), lists);
        return lists;
    }

    private void getCombinationSum(int[] candidates, int pos, int target, List<Integer> list, List<List<Integer>> lists) {
        if (target < 0)
            return;
        if (target == 0) {
            lists.add(new ArrayList<>(list));
            return;
        }
        for (int i = pos; i < candidates.length; i++) {
            list.add(candidates[i]);
            getCombinationSum(candidates, i, target - candidates[i], list, lists);
            list.remove(list.size() - 1);
        }
    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        // 有重复元素 只能使用一次
        Arrays.sort(candidates);
        List<List<Integer>> lists = new ArrayList<>();
        getCombinationSum2(candidates, 0, target, new ArrayList<>(), lists);
        return lists;
    }

    private void getCombinationSum2(int[] candidates, int pos, int target, List<Integer> list, List<List<Integer>> lists) {
        if (target < 0)
            return;
        if (target == 0) {
            lists.add(new ArrayList<>(list));
            return;
        }
        for (int i = pos; i < candidates.length; i++) {
            if (i > pos && candidates[i] == candidates[i - 1])
                continue;
            list.add(candidates[i]);
            getCombinationSum2(candidates, i + 1, target - candidates[i], list, lists);
            list.remove(list.size() - 1);
        }
    }

    /**
     * mid 64. 最小路径和
     */
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for (int i = 1; i < m; i++) {
            grid[i][0] += grid[i - 1][0];
        }
        for (int i = 1; i < n; i++) {
            grid[0][i] += grid[0][i - 1];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        return grid[m - 1][n - 1];
    }

    /**
     * 48. 旋转图像
     */
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        // 定义四个方向
        int[][] dirs = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        // len 代表正方形的边长
        for (int len = n, start = 0; len >= 2; len -= 2, start++) {
            int beginX = start, beginY = start;
            int endX = beginX + len - 1, endY = beginY + len - 1;
            // 循环 len - 1 次，每次把四条边上的四个点旋转
            for (int i = 0; i < len - 1; i++) {
                int[] upLeft = {beginX, beginY + i};
                int[] upRight = {beginX + i, endY};
                int[] downRight = {endX, endY - i};
                int[] downLeft = {endX - i, beginY};
                int tempUpLeft = matrix[upLeft[0]][upLeft[1]];
                matrix[upLeft[0]][upLeft[1]] = matrix[downLeft[0]][downLeft[1]];
                matrix[downLeft[0]][downLeft[1]] = matrix[downRight[0]][downRight[1]];
                matrix[downRight[0]][downRight[1]] = matrix[upRight[0]][upRight[1]];
                matrix[upRight[0]][upRight[1]] = tempUpLeft;
            }
        }
    }

    /**
     * 128. 最长连续序列
     */
    public int longestConsecutive(int[] nums) {
        int max = 0;
        // 用一个 map: key=数字 value=序列长度
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            if (map.containsKey(num))
                continue;
            int smaller = map.getOrDefault(num - 1, 0);
            int bigger = map.getOrDefault(num + 1, 0);
            int total = smaller + bigger + 1;
            map.put(num, total);
            map.put(num - smaller, total);
            map.put(num + bigger, total);
            max = Math.max(max, total);
        }
        return max;
    }

    /**
     * 240. 搜索二维矩阵 II
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int x = 0, y = n - 1;
        while (x < m && y >= 0) {
            if (matrix[x][y] == target)
                return true;
            if (matrix[x][y] < target)
                x++;
            else
                y--;
        }
        return false;
    }

    /**
     * 221. 最大正方形
     */
    public int maximalSquare(char[][] matrix) {
        int maxLen = 0;
        int m = matrix.length, n = matrix[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == '1') {
                dp[i][0] = 1;
                maxLen = 1;
            }
        }
        for (int i = 0; i < n; i++) {
            if (matrix[0][i] == '1') {
                dp[0][i] = 1;
                maxLen = 1;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == '0')
                    continue;
                int min = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1]));
                dp[i][j] = 1 + min;
                maxLen = Math.max(maxLen, dp[i][j]);
            }
        }
        return maxLen * maxLen;
    }

    /**
     * 695. 岛屿的最大面积
     */
    public int maxAreaOfIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int maxArea = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1)
                    maxArea = Math.max(maxArea, getIslandArea(grid, i, j));
            }
        }
        return maxArea;
    }

    private int getIslandArea(int[][] grid, int i, int j) {
        grid[i][j] = 0;
        // 找四个方向
        int area = 1;
        if (i - 1 >= 0 && grid[i - 1][j] == 1)
            area += getIslandArea(grid, i - 1, j);
        if (i + 1 < grid.length && grid[i + 1][j] == 1)
            area += getIslandArea(grid, i + 1, j);
        if (j - 1 >= 0 && grid[i][j - 1] == 1)
            area += getIslandArea(grid, i, j - 1);
        if (j + 1 < grid[0].length && grid[i][j + 1] == 1)
            area += getIslandArea(grid, i, j + 1);
        return area;
    }

    /**
     * 162. 寻找峰值
     */
    public int findPeakElement(int[] nums) {
        // -2^31 <= nums[i] <= 2^31 - 1
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            // 如果nums[mid]比两边大，则找到答案
            long midLeft = mid == 0 ? Long.MIN_VALUE : nums[mid - 1];
            long midRight = mid == nums.length - 1 ? Long.MIN_VALUE : nums[mid + 1];
            if (nums[mid] > midLeft && nums[mid] > midRight)
                return mid;
            // 如果nums[mid]比左面小，去左面找答案，比右面小，去右面找答案
            if (nums[mid] < midLeft) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

    /**
     * 14. 最长公共前缀
     */
    public String longestCommonPrefix(String[] strs) {
        // 1 <= strs.length <= 200
        StringBuilder sb = new StringBuilder();
        int minLen = Integer.MAX_VALUE;
        for (String str : strs) {
            minLen = Math.min(minLen, str.length());
        }
        int pos = 0;
        while (pos < minLen) {
            char c = strs[0].charAt(pos);
            boolean flag = true;
            for (int i = 1; i < strs.length; i++) {
                if (strs[i].charAt(pos) != c) {
                    flag = false;
                    break;
                }
            }
            if (!flag)
                break;
            sb.append(c);
            pos++;
        }
        return sb.toString();
    }

    /**
     * 179. 最大数
     */
    public String largestNumber(int[] nums) {
        int n = nums.length;
        String[] strs = new String[n];
        for (int i = 0; i < n; i++) {
            strs[i] = String.valueOf(nums[i]);
        }
        // 🌟
        Arrays.sort(strs, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(strs[i]);
        }
        // 去除多余的0
        while (!sb.isEmpty() && sb.charAt(0) == '0') {
            sb.deleteCharAt(0);
        }
        if (sb.isEmpty())
            sb.append('0');
        return sb.toString();
    }

    /**
     * 62. 不同路径
     */
    public int uniquePaths(int m, int n) {
        int[][] path = new int[m][n];
        for (int i = 0; i < m; i++) {
            path[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            path[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                path[i][j] = path[i - 1][j] + path[i][j - 1];
            }
        }
        return path[m - 1][n - 1];
    }

    // 不同路径2️⃣
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int len = obstacleGrid.length, wid = obstacleGrid[0].length;
        int[][] path = new int[len][wid];
        if (obstacleGrid[0][0] == 1) return 0;
        else path[0][0] = 1;
        for (int i = 1; i < len; i++) {
            if (obstacleGrid[i][0] == 0)
                path[i][0] = 1;
            else
                break;
        }
        for (int i = 1; i < wid; i++) {
            if (obstacleGrid[0][i] == 0)
                path[0][i] = 1;
            else
                break;
        }
        for (int i = 1; i < len; i++) {
            for (int j = 1; j < wid; j++) {
                if (obstacleGrid[i][j] == 0)
                    path[i][j] = (obstacleGrid[i - 1][j] == 0 ? path[i - 1][j] : 0) + (obstacleGrid[i][j - 1] == 0 ? path[i][j - 1] : 0);
            }
        }
        return path[len - 1][wid - 1];
    }

    /**
     * 198. 打家劫舍
     */
    public int rob(int[] nums) {
        // 1 <= nums.length <= 100
        int n = nums.length;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.max(nums[i - 1] + dp[i - 2], dp[i - 1]);
        }
        return dp[n];
    }

    // 打家劫舍2️⃣
    public int rob2(int[] nums) {
        // 1 <= nums.length <= 100
        int n = nums.length;
        if (n <= 3)
            return Arrays.stream(nums).max().getAsInt();
        int[] stealZero = new int[n];
        int[] noZero = new int[n];
        stealZero[0] = nums[0];
        noZero[0] = 0;
        stealZero[1] = nums[0];
        noZero[1] = nums[1];
        for (int i = 2; i < n; i++) {
            noZero[i] = Math.max(noZero[i - 1], noZero[i - 2] + nums[i]);
            if (i == n - 1)
                stealZero[i] = stealZero[i - 1];
            else
                stealZero[i] = Math.max(stealZero[i - 1], stealZero[i - 2] + nums[i]);
        }
        return Math.max(stealZero[n - 1], noZero[n - 1]);
    }

    // 打家劫舍3️⃣map表示dp
    public int rob3(TreeNode root) {
        // 用了两个map表示两个“dp数组”：1.选择当前根节点的最大值 2.不选择当前根节点的最大值
        Map<TreeNode, Integer> choose = new HashMap<>();
        Map<TreeNode, Integer> no = new HashMap<>();
        choose.put(null, 0);
        no.put(null, 0);
        robTree(root, choose, no);
        return Math.max(choose.get(root), no.get(root));
    }

    private void robTree(TreeNode node, Map<TreeNode, Integer> choose, Map<TreeNode, Integer> no) {
        if (node == null)
            return;
        robTree(node.left, choose, no);
        robTree(node.right, choose, no);
        int noLeft = no.get(node.left);
        int noRight = no.get(node.right);
        choose.put(node, node.val + noLeft + noRight);
        no.put(node, Math.max(choose.get(node.left), noLeft) + Math.max(choose.get(node.right), noRight));
    }

    // 打家劫舍3️⃣🌟map表示dp-使用一个map——最符合直觉
    public int rob3_map(TreeNode root) {
        Map<TreeNode, Integer> dp = new HashMap<>();
        dp.put(null, 0);
        robTree(root, dp);
        return dp.get(root);
    }

    private void robTree(TreeNode node, Map<TreeNode, Integer> dp) {
        if (node == null)
            return;
        robTree(node.left, dp);
        robTree(node.right, dp);
        // 考虑左右子是否存在
        int choose = 0, no = 0;
        if (node.left != null && node.right != null) {
            choose = node.val + dp.get(node.left.left) + dp.get(node.left.right) + dp.get(node.right.left) + dp.get(node.right.right);
            no = dp.get(node.left) + dp.get(node.right);
        } else if (node.left != null) {
            choose = node.val + dp.get(node.left.left) + dp.get(node.left.right);
            no = dp.get(node.left);
        } else if (node.right != null) {
            choose = node.val + dp.get(node.right.left) + dp.get(node.right.right);
            no = dp.get(node.right);
        } else {
            choose = node.val;
        }
        dp.put(node, Math.max(choose, no));
    }

    // 打家劫舍3️⃣数组传递dp
    public int rob3_(TreeNode root) {
        int[] rootList = robTree(root);
        return Math.max(rootList[0], rootList[1]);
    }

    private int[] robTree(TreeNode node) {
        if (node == null)
            return new int[]{0, 0}; // int[0] 表示选择这个节点 int[1] 表示不选择这个节点
        int[] left = robTree(node.left);
        int[] right = robTree(node.right);
        int[] now = new int[2];
        now[0] = node.val + left[1] + right[1];
        now[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return now;
    }

    /**
     * 152. 乘积最大子数组
     */
    public int maxProduct(int[] nums) {
        // 维护当前结尾的最大正数和最大负数
        int len = nums.length;
        int[] max = new int[len];
        int[] min = new int[len];
        max[0] = nums[0];
        min[0] = nums[0];
        int ans = nums[0];
        for (int i = 1; i < len; i++) {
            int num = nums[i];
            max[i] = Math.max(Math.max(num * max[i - 1], num * min[i - 1]), num);
            min[i] = Math.min(Math.min(num * max[i - 1], num * min[i - 1]), num);
            ans = Math.max(ans, max[i]);
        }
        return ans;
    }

    /**
     * 560. 和为 K 的子数组※
     */
    public int subarraySum(int[] nums, int k) {
        // 方法一：暴力枚举，O(n^2)复杂度
        int count = 0;
        for (int start = 0; start < nums.length; ++start) {
            int sum = 0;
            for (int end = start; end >= 0; --end) {
                sum += nums[end];
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }

    public int subarraySum_(int[] nums, int k) {
        // 方法二：哈希表+前缀和
        // 方法一的问题在于每次要找他前面的所有的数字
        // 也就是[j~i]的和要等于k的个数，那先求出来前缀和
        int len = nums.length;

        int[] preSum = new int[len];
        preSum[0] = nums[0];
        for (int i = 1; i < len; i++) {
            preSum[i] = preSum[i - 1] + nums[i];
        }
        Map<Integer, Integer> map = new HashMap<>(); // key：前缀和  value：次数
        map.put(0, 1);

        int ans = 0;
        for (int i = 0; i < len; i++) {
            ans += map.getOrDefault(preSum[i] - k, 0);
            map.put(preSum[i], map.getOrDefault(preSum[i], 0) + 1);
        }
        return ans;
    }

    /**
     * 169. 多数元素
     */
    public int majorityElement(int[] nums) {
        // 投票
        int majority = 0;
        int majorNum = 0;
        for (int num : nums) {
            if (majorNum == 0) {
                majority = num;
                majorNum++;
            } else {
                if (num == majority)
                    majorNum++;
                else
                    majorNum--;
            }
        }
        return majority;
    }

    /**
     * 227. 基本计算器 II
     */
    public int calculate(String s) {
        Deque<Integer> numStack = new ArrayDeque<>();
        Deque<Character> opStack = new ArrayDeque<>();
        // 运算符优先级
        Map<Character, Integer> map = new HashMap<>();
        map.put('+', 1);
        map.put('-', 1);
        map.put('*', 2);
        map.put('/', 2);
        // 处理空格和负数
        s = s.replace(" ", "");
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '-' && (i == 0 || s.charAt(i - 1) == '('))
                sb.append('0');
            sb.append(s.charAt(i));
        }
        s = sb.toString();
        // 遍历s进行运算
        int len = s.length();
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                int num = 0;
                int pos = i;
                while (pos < len && Character.isDigit(s.charAt(pos))) {
                    num = 10 * num + (s.charAt(pos) - '0');
                    pos++;
                }
                i = pos - 1;
                numStack.push(num);
            } else if (c == '(') {
                opStack.push(c);
            } else if (c == ')') {
                while (!opStack.isEmpty() && opStack.peek() != '(')
                    compute(numStack, opStack);
                opStack.pop();
            } else {
                // 操作符，如果这个操作符比前一个操作符级别高，那么不计算，否则计算
                while (!opStack.isEmpty() && opStack.peek() != '(' && map.get(c) <= map.get(opStack.peek()))
                    compute(numStack, opStack);
                opStack.push(c);
            }
        }
        while (!opStack.isEmpty())
            compute(numStack, opStack);
        return numStack.peek();
    }

    private void compute(Deque<Integer> numStack, Deque<Character> opStack) {
        int a1 = numStack.pop();
        int a2 = numStack.pop();
        char op = opStack.pop();
        switch (op) {
            case '+' -> numStack.push(a2 + a1);
            case '-' -> numStack.push(a2 - a1);
            case '*' -> numStack.push(a2 * a1);
            case '/' -> numStack.push(a2 / a1);
        }
    }

    /**
     * 209. 长度最小的子数组
     */
    public int minSubArrayLen(int target, int[] nums) {
        int len = nums.length;
        int minLen = Integer.MAX_VALUE;
        int left = 0, right = 0;
        int sum = 0;
        while (right < len) {
            sum += nums[right];
            while (left <= right && sum >= target) {
                minLen = Math.min(minLen, right - left + 1);
                sum -= nums[left];
                left++;
            }
            right++;
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }

    /**
     * 139. 单词拆分
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        int len = s.length();
        boolean[] dp = new boolean[len + 1];
        dp[0] = true;
        for (int i = 1; i <= len; i++) {
            for (String word : wordDict) {
                int wordLen = word.length();
                if (wordLen > i) continue;
                if (word.equals(s.substring(i - wordLen, i))) {
                    dp[i] = dp[i] || dp[i - wordLen];
                }
            }
        }
        return dp[len];
    }

    /**
     * 718. 最长重复子数组
     */
    public int findLength(int[] nums1, int[] nums2) {
        int len1 = nums1.length, len2 = nums2.length;
        int[][] dp = new int[len1][len2]; // 以ij结尾的最长子数组长度
        int max = 0;
        for (int i = 0; i < len1; i++) {
            if (nums1[i] == nums2[0]) {
                dp[i][0] = 1;
                max = 1;
            }
        }
        for (int i = 0; i < len2; i++) {
            if (nums1[0] == nums2[i]) {
                dp[0][i] = 1;
                max = 1;
            }
        }
        for (int i = 1; i < len1; i++) {
            for (int j = 1; j < len2; j++) {
                if (nums1[i] == nums2[j]) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                    max = Math.max(max, dp[i][j]);
                }
                dp[i][j] = nums1[i] == nums2[j] ? 1 + dp[i - 1][j - 1] : 0;
            }
        }
        return max;
    }

    /**
     * 283. 移动零
     */
    public void moveZeroes(int[] nums) {
        int len = nums.length;
        int swapPos = 0;
        for (int i = 0; i < len; i++) {
            if (nums[i] != 0) {
                int temp = nums[i];
                nums[i] = nums[swapPos];
                nums[swapPos] = temp;
                swapPos++;
            }
        }
    }
}
